package org.example.code.test2024.nine_mouth;

import java.util.Arrays;
import java.util.List;

public class test0913 {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            for(int j = 0;j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            max =Math.max(max,dp[i]);
        }
        return max;
    }

//    public int maxProduct(int[] nums) {
//        int n = nums.length;
//        int[] dp = new int[n];
//        dp[0] = nums[0];
//        for(int i = 1; i < n; i++){
//            dp[i] = Math.max(dp[i-1]*nums[i], nums[i]);
//        }
//        int max = Integer.MIN_VALUE;
//        for(int i=0;i<n;i++){
//            max = Math.max(max,dp[i]);
//        }
//        return max;
//    }

    public int maxProduct(int[] nums) {
        int n = nums.length;
        int min = nums[0];
        int max = nums[0];
        int result = nums[0];
        for(int i=1;i<n;i++){
            if(nums[i]<0){
                int t = max;
                max=min;
                min=t;
            }
            min=Math.min(nums[i],nums[i]*min);
            max=Math.max(nums[i],nums[i]*max);
            result = Math.max(max,result);
        }
        return result;
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        Arrays.sort(nums);
        for(int num : nums){
            sum += num;
        }
        if(sum%2!=0){
            return false;
        }
        int target = sum/2;
       boolean[]dp =new boolean[target+1];
        dp[0] = true;
        for(int num : nums){
            for(int i=target;i>=num;i--){
                dp[i] = dp[i]||dp[i-num];
            }
        }
        return dp[target];
    }

    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n]; // dp[i] 表示以 i 结尾的最长有效括号子串长度
        int maxLen = 0;

        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    // 如果前一个是 '('，则直接匹配
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    // 如果前一个是 ')'，且它之前的匹配的括号也是有效的
                    dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLen = Math.max(maxLen, dp[i]); // 维护最大值
            }
        }
        return maxLen;
    }

    public int singleNumber(int[] nums) {
        int result = 0;
        // 遍历数组，将所有元素进行异或运算
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    public int majorityElement(int[] nums) {
        int count = 1;
        int candidate = nums[0];
        for(int i=1;i<nums.length;i++){
            if(count==0){
                candidate = nums[i];
            }
            if(nums[i]==candidate){
                count++;
            }else{
                count--;
            }
        }
        return candidate;
    }

    public void sortColors(int[] nums) {
       int top=0,tail=nums.length-1;
       int x=0;
       while(x<=tail){
           if(nums[x]==0){
               int t = nums[x];
               nums[x]=nums[top];
               nums[top]=t;
               top++;
               x++;
           }else if(nums[x]==2){
               int t = nums[x];
               nums[x]=nums[tail];
               nums[tail]=t;
               tail--;
           }else{
               x++;
           }
       }
    }

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = n - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1, n - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }


}


